class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int left = 0;
        int right = matrix.size();
        int idx = -1;
        while(left < right)
        {
            int mid = (left+right) / 2;
            if(matrix[mid][0] <= target && matrix[mid][matrix[mid].size()-1] >= target)
            {
                idx = mid;
                break;
            }
            else if(matrix[mid][0] < target)
            {
                left = mid+1;
            }
            else if(matrix[mid][0] > target)
            {
                right = mid;
            }
        }

        if(idx == -1)
        {
            return false;
        }
        else
        {
            int begin = 0;
            int end = matrix[idx].size();
            while(begin < end)
            {
                int mid = (begin+end) / 2;
                if(matrix[idx][mid] == target)
                    return true;
                else if(matrix[idx][mid] > target)
                    end = mid;
                else
                    begin = mid+1;
            }
        }

        return false;
    }
};